package template.intermediate;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * @author ：Sei
 * @date ：Created in 2020/1/4 19:03
 * @description：树状数组模板
 * @modified By：
 * @version: $
 */
public class BinaryIndexedTreeTemplate {
    /**
     * 非负整数二进制下最低位的1与后面的0组成的数值，如lowbit(101100)=(100)b=4
     * @param n
     * @return
     */
    private int[] tree = new int[10];
    private int size;

    public BinaryIndexedTreeTemplate(int[] tree){
        this.size = tree.length;
        for (int i = 1; i < tree.length+1; i++) {
            this.add(i, tree[i-1]);
        }
    }

    private static int lowbit(int n){
        return n & (~n+1);
    }

    public void add(int x, int k, int n){
        for(;x<=n;x+=lowbit(x)){ tree[x]+=k; }
    }

    public void add(int x, int k){
        for(;x<=size;x+=lowbit(x)){ tree[x]+=k; }
    }

    public int sum(int x){
        int res = 0;
        for(;x>0;x-=lowbit(x)){ res += tree[x]; }
        return res;
    }

    public int sum(int left, int right){
        int res = 0;
        for(;right>=left;right-=lowbit(right)){ res += tree[right]; }
        return res;
    }

    public int get(int index){
        return this.tree[index];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8};
        BinaryIndexedTreeTemplate bt = new BinaryIndexedTreeTemplate(arr);
        System.out.println(Arrays.toString(bt.tree));
        bt.add(4, 4);
        bt.add(3, 7);
        System.out.println(Arrays.toString(bt.tree));
        System.out.println(bt.sum(8));
        System.out.println(bt.sum(1, 4));
        System.out.println(bt.sum(5, 1));

    }
}
